class LRUCache {
public:
    LRUCache(int capacity) 
    : _capacity(capacity)
    {

    }
    
    int get(int key) {
        auto it = _seq.find(key);
        //将_cache中的满足条件的key移动到_cache的末尾,并返回相应的value
        if(it != _seq.end())  {
            _cache.splice(_cache.begin(), _cache, it->second);
            _seq[key] = _cache.begin();
            return it->second->second;
        }
        return -1;
    }
    
    void put(int key, int value) {
        auto it = _seq.find(key);
        //使用_seq查询该key的位置,并且将其移动到_cache的首部
        if(it != _seq.end()){
            it->second->second = value;
            _cache.splice(_cache.begin(), _cache, it->second);
            return ;
        } 
        //在_cache首部生成新的key和value
        _cache.emplace_front(key, value);
        //将key的位置记录在_seq中
        _seq[key] = _cache.begin();

        //当长度大于缓冲区的容量时,把尾部存储的键值对删除
        if(_seq.size() > _capacity){
            _seq.erase(_cache.back().first);
            _cache.pop_back();
        }
        return ;
    }

private:
    //保证O(1)时间复杂度势必使用list和unordered_map
    using iterator = list<pair<int,int>>::iterator;
    unordered_map<int, iterator> _seq; //存放key和其在list中的位置
    list<pair<int,int>> _cache; //存放key和value
    int _capacity;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */